
@String{springer={Springer}}

@String{lncs={Lecture Notes in Computer Science}}

# Journal names
@String{ai={Acta Informatica}}
@String{cacm={Communications of the ACM}}
@String{jacm={Journal of the ACM}}
@String{acs={ACM Computing Surveys}}
@String{actainf={Acta Informatica}}
@String{tcs={Theoretical Computer Science}}
@String{ftdb={Foundations and Trends in Databases}}
@String{bit={BIT}}
@String{isaac02={Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02)}}
@String{soda92={Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA'92)}}
@String{wads89={Proceedings of the Algorithms and Data Structures Workshop (WADS'89)}}
@String{wads93={Proceedings of the 3rd Algorithms and Data Structures Workshop (WADS'93)}}
@String{wads99={Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99)}}
@String{jalg={Journal of Algorithms}}
@String{alg={Algorithmica}}
@String{jcss={Journal of computer and system sciences}}
@String{smd={Soviet Mathematics Doklady}}
@String{tocs={Theory of Computing Systems}}

@inproceedings{a89,
  title =	 {Improving partial rebuilding by using simple balance
                  criteria},
  author =	 {Andersson, A.},
  pages =	 {393--402},
  crossref =     {wads89proc},
}

@inproceedings{a93,
  title =	 {Balanced search trees made simple},
  author =	 {Andersson, A.},
  pages =	 {60--71},
  crossref =     {wads93proc},
}

@article{a99,
  title =	 {General balanced trees},
  author =	 {Andersson, A.},
  journal =	 jalg,
  volume =	 30,
  number =	 1,
  pages =	 {1--18},
  year =	 1999,
  publisher =	 {Elsevier}
}

@article{as96,
  title =	 {Randomized search trees},
  author =	 {Seidel, R. and Aragon, C.R.},
  journal =	 alg,
  volume =	 16,
  number =	 4,
  pages =	 {464--497},
  year =	 1996,
  publisher =	 {Springer}
}

@article{avl62,
  title =	 {An algorithm for the organization of information},
  author =	 {Adelson-Velskii, G.M. and Landis, E.M.},
  journal =	 smd,
  volume =	 3,
  number =	 {1259-1262},
  pages =	 4,
  year =	 1962
}

@inproceedings{bbg02,
  author =	 "A. Bagchi and A. L. Buchsbaum and M. T. Goodrich",
  title =	 "Biased Skip Lists.",
  pages =	 {1-13},
  crossref =     {isaac02proc}
}

@InProceedings{bcdms99,
  author =	 {A. Brodnik and S. Carlsson and E. D. Demaine and
                  J. I. Munro and R. Sedgewick},
  title =	 {Resizable Arrays in Optimal Time and Space},
  pages =	 {37--48},
  crossref =	 {wads99proc},
},

@inproceedings{bhkkr99,
  title =	 {{UMAC}: Fast and secure message authentication},
  author =	 {Black, J. and Halevi, S. and Krawczyk, H. and
                  Krovetz, T. and Rogaway, P.},
  crossref =     {crypto99proc},
  pages =	 {79--79},
}

@inproceedings{m59,
  title =	 {The Shortest Path Through a Maze},
  author =	 {E. F. Moore},
  booktitle =    {Proceedings of the International Symposium on 
                  the Theory of Switching},
  pages =	 {285--292},
  year =	 {1959}
}

@article{ht73,
  author    = {J. E. Hopcroft and R. E. Tarjan},
  title     = {Algorithm 447: Efficient Algorithms for Graph Manipulation},
  journal   = cacm,
  volume    = {16},
  number    = {6},
  year      = {1973},
  pages     = {372-378},
}

@article{ht74,
  author    = {J. E. Hopcroft and R. E. Tarjan},
  title     = {Efficient Planarity Testing},
  journal   = jacm,
  volume    = {21},
  number    = {4},
  year      = {1974},
  pages     = {549-568},
}

@article{l61,
  title =	 {An Algorithm for Path Connection and Its Applications},
  author =	 {C. Y. Lee},
  journal =      {IRE Transaction on Electronic Computers},
  volume =       {EC-10},
  number =       {3},
  pages =	 {346--365},
  year =	 {1961}
}

@inproceedings{bdl08,
  author =	 {Bose, P. and Dou\"{\i}eb, K. and Langerman, S.},
  title =	 {Dynamic optimality for skip lists and B-trees},
  pages =	 {1106--1114},
  crossref =     {soda08proc},
}

@techreport{c72,
  author =	 {Crane, C.A.},
  title =	 {Linear lists and priority queues as balanced binary trees},
  institution =  {Computer Science Department, Stanford University},
  number =       {STAN-CS-72-259}, 
  year =	 1972,
  publisher =	 {Stanford University}
}

@article{cw79,
  title =	 {Universal classes of hash functions},
  author =	 {Carter, J.L. and Wegman, M.N.},
  journal =	 jcss,
  volume =	 18,
  number =	 2,
  pages =	 {143--154},
  year =	 1979,
  publisher =	 {Elsevier}
}

@article{d88,
  title =	 {Applications of the theory of records in the study
                  of random trees},
  author =	 {Devroye, L.},
  journal =	 actainf,
  volume =	 26,
  number =	 1,
  pages =	 {123--130},
  year =	 1988,
  publisher =	 {Springer}
}

@inproceedings{d90,
  title =	 {Lower bounds for monotonic list labeling},
  author =	 {Dietz, P. and Zhang, J.},
  pages =	 {173--180},
  crossref =     {swat90proc},
}

@InProceedings{d96,
  author =	 {M. Dietzfelbinger},
  title =	 {Universal hashing and {$k$}-wise independent random
                  variables via integer arithmetic without primes},
  pages =	 {567--580},
  crossref =	 {stacs96proc},
}

@inproceedings{dgmp92,
  title =	 {Polynomial hash functions are reliable},
  author =	 {Dietzfelbinger, M. and Gil, J. and Matias, Y. and
                  Pippenger, N.},
  pages =	 {235--246},
  crossref =     {icalp92proc},
}

@article{dkkmrt94,
  author    = {M. Dietzfelbinger and
               A. R. Karlin and
               K. Mehlhorn and
               F. Meyer auf der Heide and
               H. Rohnert and
               R. E. Tarjan},
  title     = {Dynamic Perfect Hashing: Upper and Lower Bounds},
  journal   = sicomp,
  volume    = {23},
  number    = {4},
  year      = {1994},
  pages     = {738-761},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{dhkp97,
  title =	 {A Reliable Randomized Algorithm for the Closest-Pair Problem},
  author =	 {Dietzfelbinger, M. and Hagerup, T. and Katajainen,
                  J. and Penttonen, M.},
  journal =	 jalg,
  volume =	 25,
  number =	 1,
  pages =	 {19--51},
  year =	 1997,
  publisher =	 {Elsevier}
}

@inproceedings{e09,
  title =	 {Pairing Heaps with {$O(\log\log n)$} decrease Cost},
  author =	 {Elmasry, A.},
  booktitle =	 {Proceedings of the twentieth Annual ACM-SIAM
                  Symposium on Discrete Algorithms},
  pages =	 {471--476},
  year =	 2009,
  organization = {Society for Industrial and Applied Mathematics}
}

@book{e1590,
  author =	 {Eytzinger, M.},
  title =	 {Thesaurus principum hac aetate in Europa viventium
                  (Cologne)},
  year =	 1590,
  note =	 {In commentaries, `Eytzinger' may appear in variant
                  forms, including: Aitsingeri, Aitsingero,
                  Aitsingerum, Eyzingern},
}

@inproceedings{esss01,
  author =	 {Ergun, F. and Sahinalp, S. C. and Sharp,
                  J. and Sinha, R.},
  title =	 {Biased dictionaries with fast insert/deletes},
  pages =	 {483--491},
  crossref =     {stoc01proc}
}

@article{fks84,
  title =	 {Storing a sparse table with 0 (1) worst case access
                  time},
  author =	 {Fredman, M. L. and Koml{\'o}s, J. and Szemer{\'e}di,
                  E.},
  journal =	 jacm,
  volume =	 31,
  number =	 3,
  pages =	 {538--544},
  year =	 1984,
  publisher =	 {ACM}
}

@article{fsst86,
  title =	 {The pairing heap: A new form of self-adjusting heap},
  author =	 {Fredman, M.L. and Sedgewick, R. and Sleator,
                  D.D. and Tarjan, R.E.},
  journal =	 alg,
  volume =	 1,
  number =	 1,
  pages =	 {111--129},
  year =	 1986,
  publisher =	 {Springer}
}

@article{ft87,
  title =	 {Fibonacci heaps and their uses in improved network
                  optimization algorithms},
  author =	 {Fredman, M.L. and Tarjan, R.E.},
  journal =	 jacm,
  volume =	 34,
  number =	 3,
  pages =	 {596--615},
  year =	 1987,
  publisher =	 {ACM}
}

@InProceedings{gk99,
  author =	 {M. T. Goodrich and J. G. Kloss},
  title =	 {Tiered Vectors: Efficient Dynamic Arrays for
                  Rank-Based Sequences},
  pages =	 {205--216},
  crossref =	 {wads99proc},
}

@Book{gkp94,
  author =	 {R. L. Graham and D. E. Knuth and O. Patashnik},
  title =	 {Concrete Mathematics},
  publisher =	 {Addison-Wesley},
  year =	 1994,
  edition =	 {2nd}
}

@inproceedings{gm98,
  title =	 {Randomized meldable priority queues},
  author =	 {Gambin, A. and Malinowski, A.},
  booktitle =	 {SOFSEM’98: Theory and Practice of Informatics},
  pages =	 {344--349},
  year =	 1998,
  organization = {Springer}
}

@inproceedings{gr93,
  title =	 {Scapegoat trees},
  author =	 {Galperin, I. and Rivest, R.L.},
  pages =	 {165--174},
  crossref =     {soda93proc},
  }

@inproceedings{gs78,
  title =	 {A dichromatic framework for balanced trees},
  author =	 {Guibas, L.J. and Sedgewick, R.},
  pages =	 {8--21},
  crossref =     {focs78proc},
  }

@Misc{hashing,
  title =	 {Bibliography on Hashing},
  url =          {http://liinwww.ira.uka.de/bibliography/Theory/hash.html},
  key =		 {bibliography on hashing},
  lastchecked =	 {2011-07-20}
}

@Misc{hpux,
  title =	 {{HP-UX} Process Management White Paper, Version 1.3},
  institution =	 {Hewlett-Packard Company},
  key =		 {hpux},
  number =	 {5965-4642},
  year =	 1997,
  url =          {http://h21007.www2.hp.com/portal/download/files/prot/files/STK/pdfs/proc_mgt.pdf},
  lastchecked =	 {2011-07-20}
}

@Book{k97v1,
  author =	 {D. Knuth},
  title =	 {Fundamental Algorithms},
  series =	 {The Art of Computer Programming},
  volume =	 1,
  edition =	 {Third},
  year =	 1997,
  publisher =	 {Addison-Wesley}
}

@Book{k97v2,
  author =	 {D. Knuth},
  title =	 {Seminumerical Algorithms},
  series =	 {The Art of Computer Programming},
  volume =	 2,
  edition =	 {Third},
  year =	 1997,
  publisher =	 {Addison-Wesley}
}

@Book{k97v3,
  author =	 {D. Knuth},
  title =	 {Sorting and Searching},
  series =	 {The Art of Computer Programming},
  volume =	 3,
  edition =	 {Second},
  year =	 1997,
  publisher =	 {Addison-Wesley}
}

@Article{kmp95,
  author =	 {P. Kirschenhofer and C. Martinez and H. Prodinger},
  title =	 {Analysis of an optimized search algorithm for skip
                  lists},
  journal =	 tcs,
  volume =	 144,
  pages =	 {199--220},
  year =	 1995,
}

@Article{kp94,
  author =	 {P. Kirschenhofer and H. Prodinger},
  title =	 {The path length of random skip lists},
  journal =	 actainf,
  volume =	 31,
  pages =	 {775--792},
  year =	 1994,
}

@inproceedings{mps92,
  author =	 {J. I. Munro and T. Papadakis and R. Sedgewick},
  title =	 {Deterministic skip lists},
  pages =	 {367--375},
  crossref =	 {soda92proc},
}

@Manual{oracle_collections,
  title =	 {The Collections Framework},
  organization = {Oracle},
  url =          {http://download.oracle.com/javase/1.5.0/docs/guide/collections/},
  lastchecked =	 {2011-07-19}
}

@Manual{oracle_jdk6,
  title =	 {Java Platform Standard Ed. 6},
  organization = {Oracle},
  url =		 {http://download.oracle.com/javase/6/docs/api/},
  lastchecked =	 {2011-07-19}
}

@Manual{oracle_tutorials,
  title =	 {The Java Tutorials},
  organization = {Oracle},
  url =		 {http://download.oracle.com/javase/tutorial/},
  lastchecked =	 {2011-07-19}
}

@TechReport{p89,
  author =	 {W. Pugh},
  title =	 {A Skip List Cookbook},
  institution =	 {Institute for Advanced Computer Studies, Department
                  of Computer Science},
  year =	 1989,
  key =		 {UMIACS-TR-89-72.1},
  address =	 {University of Maryland, College Park},
  url =		 {ftp://ftp.cs.umd.edu/pub/skipLists/cookbook.pdf},
  lastchecked =	 {2011-07-20}
}

@Article{p91,
  author =	 {W. Pugh},
  title =	 {Skip lists: A Probabilistic Alternative to Balanced
                  Trees},
  journal =	 cacm,
  volume =	 33,
  number =	 6,
  pages =	 {668--676},
  year =	 1990
}

@Article{pmp92,
  author =	 {T. Papadakis and J. I. Munro and P. V. Poblete},
  title =	 {Average search and update costs in skip lists},
  journal =	 bit,
  volume =	 32,
  pages =	 {316--332},
  year =	 1992
}

@article{pr04,
  title =	 {Cuckoo hashing},
  author =	 {Pagh, R. and Rodler, F.F.},
  journal =	 jalg,
  volume =	 51,
  number =	 2,
  pages =	 {122--144},
  year =	 2004,
  publisher =	 {Elsevier}
}

@article{pt12,
  author =	 {P{\v a}tra{\c s}cu, M. and Thorup, M.},
  title     = {The Power of Simple Tabulation Hashing},
  journal   = jacm,
  volume    = {59},
  number    = {3},
  year      = {2012},
  pages     = {14},
}

@book{r01,
  author =	 {S. M. Ross},
  title =	 {Probability Models for Computer Science},
  year =	 2001,
  publisher =	 {Academic Press, Inc.},
  address =	 {Orlando, FL, USA},
}

@article{r03,
  title =	 {The height of a random binary search tree},
  author =	 {Reed, B.},
  journal =	 jacm,
  volume =	 50,
  number =	 3,
  pages =	 {306--332},
  year =	 2003,
}

@Misc{redis,
  title =	 {Redis},
  key =		 {redis},
  url =		 {http://redis.io/},
  lastchecked =	 {2011-07-20}
}

@misc{s08,
  title =	 {Left-leaning red-black trees},
  author =	 {Sedgewick, R.},
  month =        {September},
  year =	 2008,
  url =          {http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf},
  lastchecked =  {2011-07-21}
}

@Misc{skipdb,
  title =	 {Skip{DB}},
  key =		 {skipdb},
  url =		 {http://dekorte.com/projects/opensource/SkipDB/},
  lastchecked =	 {2011-07-20}
}
publisher={G. Kempensem},

@inproceedings{pt07,
  author =    "M. P{\v a}tra{\c s}cu and M. Thorup",
  title =     "Randomization Does Not Help Searching Predecessors",
  pages =     "555-564",
  crossref =  {soda07proc},
}


@inproceedings{st83,
  title =	 {Self-adjusting binary trees},
  author =	 {Sleator, D.D. and Tarjan, R.E.},
  pages =	 {235--245},
  crossref =     {stoc83proc},
}

@article{v78,
  title =	 {A data structure for manipulating priority queues},
  author =	 {Vuillemin, J.},
  journal =	 {Communications of the ACM},
  volume =	 21,
  number =	 4,
  pages =	 {309--315},
  year =	 1978,
  publisher =	 {ACM}
}

@article{v80,
  title =	 {A unifying look at data structures},
  author =	 {Vuillemin, J.},
  journal =	 cacm,
  volume =	 23,
  number =	 4,
  pages =	 {229--239},
  year =	 1980,
  publisher =	 {ACM}
}

@article{w64,
  title =	 {Algorithm 232: Heapsort},
  author =	 {Williams, J.W.J.},
  journal =	 cacm,
  volume =	 7,
  number =	 6,
  pages =	 {347--348},
  year =	 1964
}

@MastersThesis{s54,
  title =        {Information Sorting in the Application of Electronic
                 Digital Computers to Business Operations},
  author =       {H. H. Seward},
  school =       {Massachusetts Institute of Technology, Digital Computer Laboratory},
  number =       {R-232},
  year =         {1954}
}

@article{h61,
  author    = {C. A. R. Hoare},
  title     = {Algorithm 64: Quicksort},
  journal   = cacm,
  volume    = {4},
  number    = {7},
  year      = {1961},
  pages     = {321},
}


@article{f64,
  author    = {R. W. Floyd},
  title     = {Algorithm 245: Treesort 3},
  journal   = cacm,
  volume    = {7},
  number    = {12},
  year      = {1964},
  pages     = {701},
}

@Misc{gutenberg,
 title      = {Free e{B}ooks by {P}roject {G}utenberg},
 url        = {http://www.gutenberg.org/},
 lastchecked= {2011-10-12}
}

@article{fw93,
  author    = {M. L. Fredman and D. E. Willard},
  title     = {Surpassing the Information Theoretic Bound with Fusion Trees},
  journal   = jcss,
  volume    = {47},
  number    = {3},
  year      = {1993},
  pages     = {424-436},
}

@article{w83,
  author    = {D. E. Willard},
  title     = {Log-Logarithmic Worst-Case Range Queries are Possible in
               Space {$\Theta(N)$}},
  journal   = ipl,
  volume    = {17},
  number    = {2},
  year      = {1983},
  pages     = {81-84},
}

@Book{llm11,
  author    = {E. Lehman and F. T. Leighton and A. R. Meyer},
  title     = {Mathematics for Computer Science},
  year      = {2011},
  url       = {http://courses.csail.mit.edu/6.042/spring12/mcs.pdf},
  lastchecked= {2012-09-06}
}

@article{mr98,
  author    = {C. Mart\'{\i}nez and S. Roura},
  title     = {Randomized Binary Search Trees},
  journal   = jacm,
  volume    = {45},
  number    = {2},
  year      = {1998},
  pages     = {288-323},
}  


@book{t14,
  author    = {S. P. Thompson},
  title     = {Calculus Made Easy},
  year      = {1914},
  publisher = {MacMillan},
  address   = {Toronto},
  note      = {Project Gutenberg EBook 33283},
  url       = {http://www.gutenberg.org/ebooks/33283},
  lastchecked =	 {2012-06-14}
} 

@inproceedings{bm70,
  author    = {R. Bayer and E. M. McCreight},
  title     = {Organization and Maintenance of Large Ordered Indexes},
  booktitle = {SIGFIDET Workshop},
  year      = {1970},
  pages     = {107-141},
  crossref  = {sigmod70},
}

@article{g10,
  author    = {Goetz Graefe},
  title     = {Modern B-Tree Techniques},
  journal   = ftdb,
  volume    = {3},
  number    = {4},
  pages     = {203--402},
  year      = {2010},
}

@article{c79,
  author    = {D. Comer},
  title     = {The Ubiquitous {B}-Tree},
  journal   = acs,
  volume    = {11},
  number    = {2},
  year      = {1979},
  pages     = {121-137},
}

@article{jp08,
  author    = {M. S. Jensen and R. Pagh},
  title     = {Optimality in External Memory Hashing},
  journal   = alg,
  volume    = {52},
  number    = {3},
  year      = {2008},
  pages     = {403-411},
}

@article{av88,
  author    = {A. Aggarwal and J. S. Vitter},
  title     = {The Input/Output Complexity of Sorting and Related Problems},
  journal   = cacm,
  volume    = {31},
  number    = {9},
  year      = {1988},
  pages     = {1116-1127},
}

@inproceedings{cw03,
  title={Denial of service via algorithmic complexity attacks},
  author={Crosby, S.A. and Wallach, D.S.},
  booktitle={Proceedings of the 12th USENIX Security Symposium},
  pages={29--44},
  year={2003},
}

@techreport{ieee754,
    address = {3 Park Avenue, New York, NY 10016-5997, USA},
    booktitle = {IEEE Std 754-2008},
    day = {29},
    doi = {10.1109/IEEESTD.2008.4610935},
    institution = {Microprocessor Standards Committee of the IEEE Computer Society},
    isbn = {978-0-7381-5752-8},
    journal = {IEEE Std 754-2008},
    keywords = {ch3, gpgpu},
    month = "August",
    organization = {Microprocessor Standards Committee of the IEEE Computer Society},
    pages = {1--58},
    title = {{IEEE Standard for Floating-Point Arithmetic}},
    urlx = {http://dx.doi.org/10.1109/IEEESTD.2008.4610935},
    year = {2008}
}

@article {ekz76,
   author = {van Emde Boas, P. and Kaas, R. and Zijlstra, E.},
   title = {Design and implementation of an efficient priority queue},
   journal = tocs,
   issn = {1432-4350},
   keyword = {Computer Science},
   pages = {99--127},
   volume = {10},
   issue = {1},
   urlx = {http://dx.doi.org/10.1007/BF01683268},
   note = {10.1007/BF01683268},
   year = {1976}
}

@article{e77,
  author    = {Peter van Emde Boas},
  title     = {Preserving Order in a Forest in Less Than Logarithmic Time
               and Linear Space},
  journal   = ipl,
  volume    = {6},
  number    = {3},
  year      = {1977},
  pages     = {80-82},
  ee        = {http://dx.doi.org/10.1016/0020-0190(77)90031-X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{s04,
  author   = {Prokash Sinha},
  title    = {A Memory-Efficient Doubly Linked List},
  journal  = {Linux Journal},
  volume   = 129,
  year     = 2005,
  url      = {http://www.linuxjournal.com/article/6828},
  lastchecked  = {2013-06-05}
}

@inproceedings{sra94,
  author    = {Zhong Shao and
               John H. Reppy and
               Andrew W. Appel},
  title     = {Unrolling Lists},
  booktitle = {Proceedings of the 1994 ACM conference LISP and Functional Programming (LFP'94)},
  year      = {1994},
  pages     = {185-195},
  publisher = {ACM},
  address   = {New York},
  ee        = {http://doi.acm.org/10.1145/182409.182453},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

